package the.offer.leetcode;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class SolutionOfBitOpt {


    /**
     * 78. 子集
     * 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
     */
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<Integer>());
        int size = nums.length;
        int subsize = (int) Math.pow(2, size);
        int hash = 1;
        while (hash < subsize) {
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                int j = 1 << i;
                if ((j & hash) == 1) {
                    temp.add(nums[i]);
                }
            }
            subsets.add(temp);
            hash++;
        }
        return subsets;
    }


    public static void main(String[] args) {
        List<List<Integer>> subsets = subsets(new int[]{1, 2, 3});
        System.out.println(subsets.toString());
    }
}
